'''
https://leetcode.cn/problems/shortest-distance-from-all-buildings
'''
from collections import deque
from typing import List


class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        distance = [[0] * n for _ in range(m)]
        house_cnt = [[0] * n for _ in range(m)]
        def bfs(i, j):
            q = deque([(i, j)])
            step = 0
            visited = [[False] * n for _ in range(m)]
            while q:
                for _ in range(len(q)):
                    i, j = q.popleft()
                    if visited[i][j]: continue
                    visited[i][j] = True
                    house_cnt[i][j] += 1
                    distance[i][j] += step
                    for tx, ty in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                        if 0<=tx<m and 0<=ty<n and grid[tx][ty] == 0:
                            q.append((tx, ty))
                step += 1

        n_house = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    n_house += 1
                    bfs(i, j)
        res = float('inf')
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and house_cnt[i][j] == n_house:
                    res = min(res, distance[i][j])
        return -1 if res == float('inf') else res

# grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
grid = [[1,0]]
print(Solution().shortestDistance(grid))
